package 简单.树;

import util.TreeNode;

/**
 * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意
 * 两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/diameter-of-binary-tree/?plan=leetcode_75&plan_progress=s9nullg
 */
public class 二叉树的直径_543 {

    public static void main(String[] args) {

        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;

        二叉树的直径_543 obj = new 二叉树的直径_543();
        System.out.println(obj.diameterOfBinaryTree(node1));

    }

    private int maxLen = 0;

    public int diameterOfBinaryTree(TreeNode root) {

        dfs(root);

        return maxLen;
    }

    // 返回值为当前节点的最大深度
    private int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftLen = dfs(node.left);
        int rightLen = dfs(node.right);

        maxLen = Math.max(maxLen, leftLen + rightLen);

        // 当前节点最大深度 = 当前节点 1 + 左右子节点深度较大的节点
        return Math.max(leftLen, rightLen) + 1;
    }

}
